;CWL:<403-INET>INQ.MAC.40303  9-Mar-82 19:33:21, Edit by CLYNN
;<403-INET>INQ.MAC.40301 29-Jan-82 15:13:58, Edit by CLYNN
; Updated for IP release 3

	SEARCH	INPAR,PROLOG
	TTITLE	INQ
	SUBTTL	Internet Queue Handling Routines, Wm. W. Plummer, 4Mar79
	SWAPCD

COMMENT	!

	Queues are double linked lists.  The left half word points
	back to the previous item and the right half word points
	forward to the next item.  Each queue has a head which
	looks like any other item.  When a queue is empty, the
	previous and next pointers of the head both point at the
	head itself.
	!


COMMENT	!

* INITQ ....  2 ...... Initialize a queue head
* CLEARQ ...  2 ...... Clear a queue. Return the items to free storage
* EMPTYQ ...  2 ...... Tells if a queue is empty or not
* NQ .......  3 ...... Places an item on a queue
* DQ .......  3 ...... Removes an item from a queue
	!

; Initialize a queue head

;T1/	(Extended) Pointer to the queue head
;
;	CALL INITQ
;Ret+1:	always

INITQ::	TEMP <QHEAD>
	STOR QHEAD,QPREV,(QHEAD) ; Make previous(head) point to the head
	STOR QHEAD,QNEXT,(QHEAD) ; Make next(head) point to the head
	RESTORE
	RET



; Clear a queue between two items

; The items themselves are not removed.  A common use is to make the
;  "from" and "to" pointer both be the queue head in order to clear
;  all items off the queue.

;T1/	(Extended) "From" item pointer
;T2/	(Extended) "To" item pointer
;
;	CALL CLEARQ
;Ret+1:	always

CLEARQ::LOCAL <FROM,TO>
	DMOVEM T1,FROM		; T1, T2 to FROM, TO

CLRQ1:	LOAD T1,QNEXT,(FROM)	; Get pointer to next item?
	SETSEC T1,INTSEC	; Make into extended pointer
	CAMN T1,TO		; Points to the last one?
	 EXIT CLRQX		; Yes.  Get out.
	CALL DQ			; Remove it from the queue (value is T1)
	CALL RETBLK		; Return block to free storage
	JRST CLRQ1

CLRQX:	RESTORE
	RET

; Add an item to a queue just to the left of another item.

; Usual application is where the other item is the queue head.  This
;  has the effect of adding the new item to the end of the queue.

;T1/	(Extended) Item pointer
;T2/	(Extended) Queue head pointer
;
;	CALL NQ	
;Ret+1:	always, value is the new item.

NQ::	TEMP <ITEM,QHEAD,PREV>
	SKIPE 0(ITEM)
	 INBUG(HLT,<EnQ: Item not dequeued>,INTNQ1)
	STOR QHEAD,QNEXT,(ITEM)	; Make Item point forward to the head
	LOAD PREV,QPREV,(QHEAD)	; Pointer to thing to left of head
	SETSEC PREV,INTSEC	; Make into extended pointer
	STOR PREV,QPREV,(ITEM)	; Is now to the left of new item
	STOR ITEM,QNEXT,(PREV)	; New item is now to right of prev.
	STOR ITEM,QPREV,(QHEAD)	; and to left of the head.
	RESTORE
	RET




; Remove an item from a queue.

;T1/	(Extended) Pointer to the item to be dequeued
;
;	CALL DQ	
;Ret+1:	always.  Value is the item dequeued.  Queue slot is cleared.

DQ::	TEMP <ITEM,PREV,NEXT>
	SKIPN 0(ITEM)
	 INBUG(HLT,<DeQ: Item not queued>,INTNQ2)
	LOAD PREV,QPREV,(ITEM)
	SETSEC PREV,INTSEC		; Make extended address
	LOAD NEXT,QNEXT,(ITEM)
	SETSEC NEXT,INTSEC	; Make into extended pointer
	STOR NEXT,QNEXT,(PREV)
	STOR PREV,QPREV,(NEXT)
	SETZM 0(ITEM)		; Indicate this item not queued.
	RESTORE
	RET

	TNXEND